MAPPING = "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        n = len(digits)
        if n == 0:
            return []
        ans = []
        path = [''] * n # 注意 path 长度一开始就是 n，不是空列表
        def dfs(i):
            if i == n:
                ans.append(''.join(path))
                return #回溯i
            for c in MAPPING[int(digits[i])]:# 递归返回后，外层循环继续执行，自动选取下一个字母，当 dfs(i+1) 执行完毕后，控制权自动返回到当前层
                path[i] = c
                dfs(i + 1)
        dfs(0)
        return ans